package se.sudoku;


import java.util.Random;

import android.util.Log;


public class generator {
		
		private boolean conflict;
		
		private int[] solution;
		private int[] puzzle;
		
		public generator(int diff) {

			int difficulties[][][] = zeros(5,9,9);
			difficulties = puzzle(diff);
			//difficulties[ difficulties[4][0][0] ] //hardest calculated difficulty
			//difficulties[ 4 ] //information
			//difficulties[ 0 ] //solution
			
			if (diff>difficulties[4][0][0])
				diff = difficulties[4][0][0];
			
			solution = new int[81];
			puzzle = new int[81];
			
			solution = getArray(difficulties[0]);
			puzzle = getArray(difficulties[ difficulties[4][0][0] ]);
			
		}
		
		public int[] zeros(int size) {

			int[] vector = new int[9];
			for (int i = 0; i < size; i++) {
				vector[i] = 0;
			}
			return vector;
		}

		public int[][] zeros(int rowSize, int colSize) {

			int[][] grid = new int[9][9];
			for (int i = 0; i < rowSize; i++) {
				for (int j = 0; j < colSize; j++) {
					grid[i][j] = 0;
				}
			}
			return grid;
		}

		public int[][][] zeros(int rowSize, int colSize, int depthSize) {

			int[][][] grid = new int[9][9][9];
			for (int i = 0; i < rowSize; i++) {
				for (int j = 0; j < colSize; j++) {
					for (int k = 0; k < depthSize; k++) {
						grid[i][j][k] = 0;
					}
				}
			}
			return grid;
		}

		public int[][][] ones(int rowSize, int colSize, int depthSize) {

			int[][][] grid = new int[9][9][9];
			for (int i = 0; i < rowSize; i++) {
				for (int j = 0; j < colSize; j++) {
					for (int k = 0; k < depthSize; k++) {
						grid[i][j][k] = 1;
					}
				}
			}
			return grid;
		}	
		
		public int sum(int[] array) {

			int size = array.length;
			int sum = 0;

			for (int i = 0; i < size; i++) {
				sum = sum + array[i];
			}
			return sum;
		}

		public int[] increase(int[] current) {

			if (current[0] < 9)
				current[0] = current[0] + 1;
			else {
				current[1] = current[1] + 1;
				current[0] = 1;
			}
			return current;
		}

		public int[] decrease(int[] current) {

			if (current[0] > 1)
				current[0] = current[0] - 1;
			else {
				current[1] = current[1] - 1;
				current[0] = 9;
			}
			return current;
		}

		public int findBlock(int[] current) {

			int block = 0;
			
			if (current[0] >= 1 && current[0] <= 3) {
				if (current[1] >= 1 && current[1] <= 3) {
					block = 1;
				}
				if (current[1] >= 4 && current[1] <= 6) {
					block = 2;
				}
				if (current[1] >= 7 && current[1] <= 9) {
					block = 3;
				}
			}

			if (current[0] >= 4 && current[0] <= 6) {
				if (current[1] >= 1 && current[1] <= 3) {
					block = 4;
				}
				if (current[1] >= 4 && current[1] <= 6) {
					block = 5;
				}
				if (current[1] >= 7 && current[1] <= 9) {
					block = 6;
				}
			}

			if (current[0] >= 7 && current[0] <= 9) {
				if (current[1] >= 1 && current[1] <= 3) {
					block = 7;
				}
				if (current[1] >= 4 && current[1] <= 6) {
					block = 8;
				}
				if (current[1] >= 7 && current[1] <= 9) {
					block = 9;
				}
			}
			
			return block;
		}

		public int[][] findNeighbors(int block) {

			int[][] neighbors = new int[9][2];

			if (block == 1) {
				int temp[][] = { { 1, 1 }, { 1, 2 }, { 1, 3 }, { 2, 1 }, { 2, 2 },
						{ 2, 3 }, { 3, 1 }, { 3, 2 }, { 3, 3 } };
				neighbors = temp;
			}
			if (block == 2) {
				int temp[][] = { { 1, 4 }, { 1, 5 }, { 1, 6 }, { 2, 4 }, { 2, 5 },
						{ 2, 6 }, { 3, 4 }, { 3, 5 }, { 3, 6 } };
				neighbors = temp;
			}
			if (block == 3) {
				int temp[][] = { { 1, 7 }, { 1, 8 }, { 1, 9 }, { 2, 7 }, { 2, 8 },
						{ 2, 9 }, { 3, 7 }, { 3, 8 }, { 3, 9 } };
				neighbors = temp;
			}

			if (block == 4) {
				int temp[][] = { { 4, 1 }, { 4, 2 }, { 4, 3 }, { 5, 1 }, { 5, 2 },
						{ 5, 3 }, { 6, 1 }, { 6, 2 }, { 6, 3 } };
				neighbors = temp;
			}
			if (block == 5) {
				int temp[][] = { { 4, 4 }, { 4, 5 }, { 4, 6 }, { 5, 4 }, { 5, 5 },
						{ 5, 6 }, { 6, 4 }, { 6, 5 }, { 6, 6 } };
				neighbors = temp;
			}
			if (block == 6) {
				int temp[][] = { { 4, 7 }, { 4, 8 }, { 4, 9 }, { 5, 7 }, { 5, 8 },
						{ 5, 9 }, { 6, 7 }, { 6, 8 }, { 6, 9 } };
				neighbors = temp;
			}

			if (block == 7) {
				int temp[][] = { { 7, 1 }, { 7, 2 }, { 7, 3 }, { 8, 1 }, { 8, 2 },
						{ 8, 3 }, { 9, 1 }, { 9, 2 }, { 9, 3 } };
				neighbors = temp;
			}
			if (block == 8) {
				int temp[][] = { { 7, 4 }, { 7, 5 }, { 7, 6 }, { 8, 4 }, { 8, 5 },
						{ 8, 6 }, { 9, 4 }, { 9, 5 }, { 9, 6 } };
				neighbors = temp;
			}
			if (block == 9) {
				int temp[][] = { { 7, 7 }, { 7, 8 }, { 7, 9 }, { 8, 7 }, { 8, 8 },
						{ 8, 9 }, { 9, 7 }, { 9, 8 }, { 9, 9 } };
				neighbors = temp;
			}

			return neighbors;
		}

		public int[][][] checkConflicts(int[] current, int randomNumber, int[][] grid, int[][][] notAllowed) {

			conflict = false;
			int block;
			int neighbors[][] = zeros(9, 2);
			//Log.v("random", ""+randomNumber);
			
			for (int i = 0; i < 9; i++) {
				if (grid[i][current[1]-1] == grid[current[0]-1][current[1]-1]) {
					if (i != current[0]-1) {
						// column conflict
						//Log.v("col conflict with number: " + grid[current[0]-1][current[1]-1],  " at: " + i + "," + current[1]);
						conflict = true;
						notAllowed[current[0]-1][current[1]-1][randomNumber-1] = 1;
					}
				}
			}

			for (int i = 0; i < 9; i++) {
				if (grid[current[0]-1][i] == grid[current[0]-1][current[1]-1]) {
					if (i != current[1]-1) {
						// row conflict
						//Log.v("row conflict", "with number : " + grid[current[0]-1][current[1]-1]);
						conflict = true;
						notAllowed[current[0]-1][current[1]-1][randomNumber-1] = 1;
					}
				}
			}

			block = findBlock(current);
			neighbors = findNeighbors(block);

			for (int i = 0; i < 9; i++) {
				if (grid [ neighbors[i][0]-1 ] [ neighbors[i][1]-1 ] == grid[current[0]-1][current[1]-1]) {
					if (neighbors[i][0]-1 != current[0]-1
							&& neighbors[i][1]-1 != current[1]-1) {
						conflict = true;
						notAllowed[current[0]-1][current[1]-1][randomNumber-1] = 1;
					}
				}
			}
			
			
			return notAllowed;
		}
			
		public int[][] generateSolution() {

			int grid[][] = zeros(9, 9);
			int notAllowed[][][] = zeros(9, 9, 9);
			int current[] = { 1, 1 };

			int counter = 0;
			
			boolean validateRandom;

			int randomNumber;
			Random generator = new Random();
			
			while (current[1] != 10) {

				conflict = true;

				while (conflict == true) {

					randomNumber = generator.nextInt(9) + 1; //1-9
					validateRandom = true;

					if (sum(notAllowed[current[0]-1][current[1]-1]) != 9) {

						while (validateRandom == true) {

							if (notAllowed[current[0]-1][current[1]-1][randomNumber-1] == 1) {
								if (randomNumber < 9)
									randomNumber = randomNumber + 1;
								else
									randomNumber = 1;
							} else {
								validateRandom = false;
							}
						}
					}
					
					grid[current[0]-1][current[1]-1] = randomNumber;

					notAllowed = checkConflicts(current, randomNumber, grid, notAllowed);
					
					
					
					counter++;
					//if(counter>2000)
					//	conflict = false; //remove

					if (sum(notAllowed[current[0]-1][current[1]-1]) == 9) {
						//Log.v("loooongcat", "generateSolution");
						notAllowed[current[0]-1][current[1]-1] = zeros(9);
						grid[current[0]-1][current[1]-1] = 0;
						decrease(current);
						notAllowed[current[0]-1][current[1]-1][grid[current[0]-1][current[1]-1]-1] = 1;
					}
				}
				increase(current);
				//Log.v("end", "" + current[1]);

			}
			//outputSum(notAllowed);
			return grid;
		}
		
		public int[][] solver(int[][] startGrid){
			
			int solved[][] = zeros(9,9);
			int solveGrid[][] = zeros(9,9);
			int possible[][][] = ones(9,9,9);
			
			int number;
			int coord[] = zeros(2);
			
			//initiate grid with known values
			for (int row = 0 ; row < 9 ; row++) {
				for (int col = 0 ; col < 9 ; col++) {
					
					if(startGrid[row][col] != 0) {
						
						number = startGrid[row][col];
						solveGrid[row][col] = number;
						
						possible[row][col] = zeros(9);
						possible[row][col][number-1] = 1;
						
						coord[0] = row+1;
						coord[1] = col+1;

						possible = insertCertain(possible, number, coord);					
						
					}
					
				}
			}
							
			int prevGrid[][] = zeros(9,9);
			
			boolean stop = false;
			while(!stop){

				prevGrid = solveGrid;
							
				/*********************
				 *SINGLETON START
				 ********************/
				int certain;
				//count possible numbers from sets of rows, columns or blocks

				//for all rows
				certain = 0;
				for (int row = 0 ; row < 9 ; row++) {

					int frequency[] = zeros(9); 
					for (int col = 0 ; col < 9 ; col++) {
						for (number = 1 ; number < 10 ; number++) { //number 1->9
							frequency[number - 1 ] = frequency[number - 1] + possible[row][col][number - 1];
						}
					}
					
					for (number = 1 ; number < 10 ; number++) { // number 1->9
						if (frequency[number - 1] == 1 && number != 0) {
							certain = number;
							
							for (int col = 0 ; col < 9 ; col++) {
								if (possible[row][col][certain - 1] == 1) {
									coord[0] = row+1;
									coord[1] = col+1;
									
									possible[row][col] = zeros(9);
									possible[row][col][certain - 1] = 1;
									possible = insertCertain(possible, certain, coord);
								}
							}
							
						}					
					}					
					
				}
				
				
				//for all columns
				certain = 0;
				for (int col = 0 ; col < 9 ; col++) {

					int frequency[] = zeros(9); //inte omdeklarera?
					for (int row = 0 ; row < 9 ; row++) {
						for (number = 1 ; number < 10 ; number++) { //number 1->9
							frequency[number - 1 ] = frequency[number - 1] + possible[row][col][number - 1];
						}
					}
					
					for (number = 1 ; number < 10 ; number++) { // number 1->9
						if (frequency[number - 1] == 1 && number != 0) {
							certain = number;
							
							for (int row = 0 ; row < 9 ; row++) {
								if (possible[row][col][certain - 1] == 1) {
									coord[0] = row+1;
									coord[1] = col+1;
									
									possible[row][col] = zeros(9);
									possible[row][col][certain - 1] = 1;
									possible = insertCertain(possible, certain, coord);
								}
							}
							
						}					
					}					
					
				}
				
				
				//for all blocks
				certain = 0;
				for (int block = 1 ; block < 10 ; block++) {

					int frequency[] = zeros(9); //inte omdeklarera?
					int neighbors[][];
					neighbors = findNeighbors(block);

					for (int i = 0 ; i < 9 ; i++) {
						for (number = 1 ; number < 10 ; number++) { //number 1->9
							frequency[number - 1 ] = frequency[number - 1] + possible[ neighbors[i][0] - 1 ] [ neighbors[i][1] - 1 ] [number - 1];
						}
					}

					for (number = 1 ; number < 10 ; number++) { // number 1->9
						if (frequency[number - 1] == 1 && number != 0) {
							certain = number;
							
							for (int i = 0 ; i < 9 ; i++) {
								if (possible[ neighbors[i][0] - 1 ][ neighbors[i][1] - 1 ][certain - 1] == 1) {
									coord[0] = neighbors[i][0];
									coord[1] = neighbors[i][1];
									
									possible[ neighbors[i][0] - 1 ] [ neighbors[i][1] - 1 ] = zeros(9);
									possible[ neighbors[i][0] - 1 ] [ neighbors[i][1] - 1][certain - 1] = 1;
									possible = insertCertain(possible, certain, coord);
								}
							}
							
						}

					}					
					
				}					

				/*********************
				 *SINGLETON END
				 ********************/

				/*********************
				 *UPDATEPOSSIBLE START
				 ********************/
				boolean stillFinding = true;
				while(stillFinding) {
					stillFinding = false;
					for (int i = 0 ; i < 9 ; i++) {
						for (int j = 0 ; j < 9 ; j++) {
							if ( sum(possible[i][j]) == 1 )
								for (int k = 1 ; k < 10 ; k++) {
									if (possible[i][j][k-1] == 1 && solveGrid[i][j] != k) {
										stillFinding = true;
										solveGrid[i][j] = k;
										coord[0] = i+1;
										coord[1] = j+1;
										possible = insertCertain(possible, k, coord);
									}								
								}							
						}
					}
				}
				
				/*********************
				 *UPDATEPOSSIBLE END
				 ********************/
				
				if (!gridChanged(solveGrid, prevGrid))
					stop = true;
				
			}
			
			solved = solveGrid;
			return solved;
			
		}
		
		public int[][][] insertCertain(int[][][] possible, int number, int[] current) {
			
			for (int row = 0 ; row < 9 ; row++) {
				if (possible[row][current[1] - 1][number - 1] == possible[current[0] - 1][current[1] - 1][number - 1])
					if (row != current[0] - 1) {
						//column
						possible[row][current[1] - 1][number - 1] = 0;
					}
			}

			for (int col = 0 ; col < 9 ; col++) {
				if (possible[current[0] - 1][col][number - 1] == possible[current[0] - 1][current[1] - 1][number - 1])
					if (col != current[1] - 1) {
						//row
						possible[current[0] - 1][col][number - 1] = 0;
					}
			}

			int neighbors[][];
			int block = findBlock(current);
			neighbors = findNeighbors(block);
			for (int i = 0 ; i < 9 ; i++) {
				if (possible[ neighbors[i][0] - 1 ] [ neighbors[i][1] - 1 ] [number - 1] == possible[current[0] - 1][current[1] - 1][number - 1])
					if (neighbors[i][0] != current[0] && neighbors[i][1] != current[1]) {
						//block
						possible[ neighbors[i][0] - 1 ] [ neighbors[i][1] - 1 ] [number - 1] = 0;
					}
			}

			return possible;
		}
		
		public boolean gridChanged(int[][] grid, int[][] prevGrid) {
			
			boolean changed = false;
			for (int row = 0 ; row < 9 ; row++)
				for (int col = 0 ; col < 9 ; col++)
					if (grid[row][col] != prevGrid[row][col])
						changed = true;
		
			return changed;				
		}
		
		public int[][][] puzzle(int numberOfDifficulties) {
			
			//[0][][] contains solution
			//[1][][] contains first difficulty
			//[2][][] contains second difficulty
			//[3][][] contains third difficulty
			//[4][][] contains information about difficulties		
			
			Random randN = new Random();
			
			long startTime = System.currentTimeMillis();
			
			int[][] grid = zeros(9,9);
			
			grid = generateSolution();
			int[][] finalPuzzle = copy(grid);
			int[][] tempPuzzle = copy(grid);
			
			int tryRandom = 0;
			int coord[] = zeros(2);
			coord[0] = 10;
			coord[1] = 10;
			int maxConsecutiveTries = 0;
			
			int difficulties[][][] = zeros(5,9,9);
			
			difficulties[0] = grid;
			difficulties[4] = zeros(9,9); //include information about difficulties
			
			int lastDifficulty = 0;

			if (numberOfDifficulties>3)
				numberOfDifficulties = 3;

			boolean end = false;
			for (int i = 1 ; i < numberOfDifficulties+1 ; i++) {
				//i basically determines difficulty
				if (i == 1)
					maxConsecutiveTries = 0;
				else if(i == 2)
					maxConsecutiveTries = 2;
				else
					maxConsecutiveTries = 4;
				
				//generate puzzle
				boolean firstPass = true;
				while(gridFullySolved(grid) || tryRandom < maxConsecutiveTries) {
					
					if(!firstPass && tryRandom == 0)
						tempPuzzle[coord[0]][coord[1]] = finalPuzzle[coord[0]][coord[1]];
					else {
						firstPass = false;
						tempPuzzle = copy(finalPuzzle);
					}
					
					int temp[] = zeros(2);
					temp[0] = randN.nextInt(9); //0-8
					temp[1] = randN.nextInt(9); //0-8
					
					while (temp[0] == coord[0] && temp[1] == coord[1]) {
						temp[0] = randN.nextInt(9);
						temp[1] = randN.nextInt(9);
					}
					coord = temp;

					tempPuzzle[coord[0]][coord[1]] = 0;
					grid = solver(tempPuzzle);
					
					if(gridFullySolved(grid)) {
						tryRandom = 0;
						finalPuzzle[coord[0]][coord[1]] = tempPuzzle[coord[0]][coord[1]];
					}
					else {
						tryRandom++;
					}
					
					if((System.currentTimeMillis() - startTime)/1000 > 15) { //Abort after 15 seconds
						end = true;
						break;
					}
					
				}
				
				known(finalPuzzle);
				difficulties[i] = copy(finalPuzzle);
				
				long totalTime = (System.currentTimeMillis() - startTime)/1000;
				Log.v("totaltime: " + totalTime, "asd");
				int totalTimeInt = (int)totalTime;
				
				difficulties[4][0][i] = known(difficulties[i]);
				difficulties[4][1][i] = totalTimeInt;
		
				lastDifficulty = i;
				difficulties[4][0][0] = lastDifficulty;
				
				if(known(finalPuzzle) < 26 || totalTime > 10) { //save computing time by not generating incredibly hard or time consuming puzzles
					break;					
				}
				
				if(end)
					break;
			}
			
			return difficulties;
		}
		
		public boolean gridFullySolved(int[][] grid) {
			
			boolean solved = true;
			for (int row = 0 ; row < 9 ; row++)
			    for (int col = 0 ; col < 9 ; col++)
			        if(grid[row][col] == 0)
			            solved = false;

			return solved;
		}
		
		public int known(int[][] grid) {
			
			int number = 0;
			for (int row = 0 ; row < 9 ; row++)
			    for (int col = 0 ; col < 9 ; col++)
			        if(grid[row][col] != 0)
			            number++;

			return number;
		}
		
		public int[][] copy(int[][] grid) {
			
			int[][] copy = zeros(9,9);
			for (int row = 0 ; row < 9 ; row++) 
			    for (int col = 0 ; col < 9 ; col++) 
			        copy[row][col] = grid[row][col]; 
			return copy;
		}
		
		public int[] getArray(int[][] grid) {
			
			int[] puzzle = new int[81];
			for (int row = 0 ; row < 9 ; row++) 
			    for (int col = 0 ; col < 9 ; col++) 
			        puzzle[row*9+col] = grid[row][col]; 
			return puzzle;
		}
		
		public int[] getSolution() {
			return solution;
		}

		public int[] getPuzzle() {
			return puzzle;
		}				
	}
